from tools_algorithm import *


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            f[i][0] = 1
        ans = 0
        for j in range(0, k + 1):
            for i in range(1, n + 1):
                for p in range(1, i):
                    if nums[i - 1] == nums[p - 1]:
                        f[i][j] = max(f[i][j], f[p][j] + 1)
                    elif j > 0:
                        f[i][j] = max(f[i][j], f[p][j - 1] + 1)
                ans = max(ans, f[i][j])
        return ans


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        h = DefaultDict(int)
        pi = [0] * n
        for i, v in enumerate(nums):
            pi[i] = h.get(v, -1)
            h[v] = i
        f = [0] * n
        for i, v in enumerate(nums):
            f[i] = 1 if pi[i] == -1 else f[pi[i]] + 1
        for _ in range(k):
            mx = 0
            h = DefaultDict(int)
            c = [0] * n
            for i, v in enumerate(nums):
                c[i] = max(mx + 1, h.get(v, -inf) + 1)
                h[v] = c[i]
                mx = max(mx, f[i])
            f = c
        return max(f)


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        h = DefaultDict(int)
        pi = [0] * n
        for i, v in enumerate(nums):
            pi[i] = h.get(v, -1)
            h[v] = i
        f = [0] * n
        for i, v in enumerate(nums):
            f[i] = 1 if pi[i] == -1 else f[pi[i]] + 1
        for _ in range(k):
            mx = 0
            h = DefaultDict(int)
            c = [0] * n
            for i, v in enumerate(nums):
                c[i] = max(mx + 1, h.get(v, -inf) + 1)
                h[v] = c[i]
                mx = max(mx, f[i])
            f = c
        return max(f)


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [0] * n
        for _ in range(k + 1):
            mx = 0
            h = DefaultDict(int)
            c = [0] * n
            for i, v in enumerate(nums):
                c[i] = max(mx + 1, h.get(v, -inf) + 1)
                h[v] = c[i]
                mx = max(mx, f[i])
            f = c
        return max(f)


s = Solution()
print(s.maximumLength(nums=[1, 2, 1, 1, 3, 2, 2, 3, 3, 3], k=3))
# [1, 1, 2, 3, 1, 2, 3, 2, 3, 4]
# [1, 2, 1, 1, 3, 2, 2, 3, 3, 3]
# [1, 2, 2, 3, 4, 4, 5, 5, 6, 7
# c = []
# for _ in range(100):
#     c.append(random.randint(1, 200))
# print(c)
